package com.example.demo.util;

/**
 * @author : shenxiang
 * @date : 2022/10/23 14:17
 * @description : 求最大子段问题
 */
public class ExampleMaxSubSum {

    public static void main(String[] args) {
        int[] arr = {100,200,-10,-20,-1,3,4,5,6,7,2,-2,2,-2,8,9,-9,94,-5,56,6,6,64,3,-200};
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        int left = 0;
        int right = arr.length-1;
        for (int i = left; i < right; i++) {
            System.out.print(arr[i]+" = ");
        }
        System.out.println("-----");
        System.out.println(MaxSubSum(arr, left, right));
        System.out.println(sum);
    }

    private static int MaxSubSum(int[] arr,int left,int right){
        int sum = 0;

        int i;
        // 分解到单个整数，不可继续分解
        if (left == right){
            if (arr[left] > 0) {
                sum = arr[left];
            } else {
                sum = 0;
            }
        } else {
            // 从left和right的中间分解数组
            // 划分的位置
            int center = (left + right) / 2;
            int leftsum = MaxSubSum(arr,left,center);
            int rightsum = MaxSubSum(arr,center + 1,right);
            // 计算包含center的最大值,判定是情形1、情形2还是情形3
            int s1 = 0;
            int lefts = 0;
            for (i = center;i >= left;i--){
                lefts = leftsum + arr[i];
                if (lefts > s1){
                    s1 = lefts;
                }
            }

            int s2 = 0;
            int rights = 0;
            for (int j = center + 1; j <= right; j++) {
                rights = rights + arr[j];
                if (rights > s2){
                    s2 = rights;
                }
            }
            sum = s1 + s2;
            if (sum < leftsum){
                sum = leftsum;
            }
            if (sum < rightsum){
                sum = rightsum;
            }
        }
        return sum;
    }
}
